public class num148 {
    //归并排序，排序链表
    public ListNode sortList(ListNode head) {
        return head == null? null : mergeSort(head);
    }

    private ListNode mergeSort(ListNode head) {
        if(head.next == null) {
            return head;
        }
        ListNode node1 = head;
        ListNode node2 = head;
        ListNode pre = null;
        while (node2 != null && node2.next != null) {
            pre = node1;
            node1 = node1.next;
            node2 = node2.next.next;
        }
        pre.next = null;//拆分成两个链表
        ListNode left = mergeSort(head);
        ListNode right = mergeSort(node1);
        return merge(left,right);
    }

    private ListNode merge(ListNode head, ListNode node1) {
        ListNode dummyhead = new ListNode();
        ListNode node = dummyhead;
        while (head != null && node1 != null) {
            if(head.val <= node1.val) {
                node.next = head;
                node = node.next;
                head = head.next;
            }else {
                node.next = node1;
                node1 = node1.next;
                node = node.next;
            }
        }
        if(head != null) {
            node.next = head;
        }
        if(node1 != null) {
            node.next = node1;
        }
        return dummyhead.next;
    }
}
